#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<algorithm>
using namespace std;

//int w[1001], v[1001], dp[1001][1001];
//int i, j, m, n;
//
//int main()
//{
//	cin >> m >> n;
//	for (i = 0; i < n; i++)
//	{
//		cin >> w[i] >> v[i] >> g[i];
//	}
//	for (i = 0; i < n; i++)
//	{
//		for (j = m; j >= v[j]; j--)
//		{
//			if (j - w[i] >= 0)
//			{
//				if (dp[j - v[j]][1] != g[i])
//				{
//					if (dp[j - v[i]][0] + v[i] > dp[j][0])
//					{
//						dp[j][0] = dp[j - v[i]][0] + v[i];
//						dp[j][1] = g[i];
//					}
//				}
//			}
//		}
//	}
//	cout << dp[m][0];
//	return 0;
//}


//int w[201], v[201], dp[1005][1005],d[201];
//int f[10001];
//int n, m, k, max, i, j;
//
//
//int main()
//{
//	int z = 0;
//	cin >> m >> n;
//	for (i = 1; i <= n; i++)
//	{
//		cin >> w[i] >> v[i] >> z;
//		d[z]++;
//		dp[z][d[z]] = i;
//		k = z > k ? z : k;
//	}
//
//	for (i = 1; i <= k; i++)
//	{
//		for (j = m; j >= 0; j--)
//		{
//			for (int x = 1; x <= d[i]; x++)
//			{
//				int pos = dp[i][x];
//				if (j >= w[pos])
//				{
//					f[j] = std::max(f[j], f[j - w[pos]] + v[pos]);
//				}
//			}
//		}
//	}
//
//	cout << f[m];
//	return 0;
//}